package solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/*
* 15 Array
*
* 用例
*   数组全是0的情况[0,0,0,0,0] -> [0,0,0]
*   数组中相邻元素相同[0,1,2,2,2,3] -> [1,2,3]
*   数组的数量小于3
* 不能使用暴力求解
* */
public class ThreeSum {


    /*
    * 官方解法
    * 排序+双指针
    * 排序可以去重
    * */
    public static List<List<Integer>> solution2(int[] num){
//        List<List<Integer>> result = new ArrayList<>();
//        if (nums.length < 3){
//            return result;
//        }
//
//        //sort array
//        Arrays.sort(nums);
//
//        for (int first = 0 ; first < nums.length ; first++){
//            if (first > 0 && nums[first] == nums[first - 1]){
//                continue;
//            }
//
//            int third = nums.length - 1;
//            int target = -nums[first];
//
//            for (int second = first + 1 ; second < nums.length ; second++){
//                if (second > first + 1 && nums[second] == nums[second - 1]){
//                    continue;
//                }
//
//                while (second < third && nums[second] + nums[third] > target){
//                    third--;
//                }
//
//                if (second == third){
//                    break;
//                }
//
//                if (nums[second] + nums[third] == target){
//                    List<Integer> list = new ArrayList<>();
//                    list.add(nums[first]);
//                    list.add(nums[second]);
//                    list.add(nums[third]);
//                    result.add(list);
//                }
//            }
//        }
//
//        return result;

//        List<List<Integer>> result = new ArrayList<>();
//        if (nums != null && nums.length > 2){
//            Arrays.sort(nums);
//
//            for (int i = 0 ; i < nums.length ; i++){
//                if (i > 0 && nums[i] == nums[i - 1]){
//                    continue;
//                }
//
//                int target = -nums[i];
//                int j = nums.length - 1;
//                for (int k = i + 1 ; k < nums.length ; k++){
//                    if (k > i + 1 && nums[k] == nums[k - 1]){
//                        continue;
//                    }
//
//                    while (j > k && nums[j] + nums[k] > target){
//                        j--;
//                    }
//
//                    if (k == j){
//                        break;
//                    }
//
//                    if (nums[j] + nums[k] == target){
//                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
//                    }
//
//                }
//            }
//        }
//
//
//        return result;

        //减少一次遍历
        List<List<Integer>> lists = new ArrayList<>();

        if (num != null && num.length >= 3){
            Arrays.sort(num);

            for (int i = 0 ; i < num.length - 1; i++){
                if (i > 0 && num[i] == num[i - 1]){
                    continue;//如果用i++ 遇到[000000]会爆炸
                }

                int j = num.length - 1;
                int target = -num[i];
                for (int k = i + 1 ; k < num.length - 1; k++){
                    if (k > i + 1 && num[k] == num[k - 1]){//使用k != i + 1 测试不过
                        continue;
                    }


                    // num[j] + num[k] != target 失效并且多循环
                    while (j > k && num[j] + num[k] > target){
                        j--;
                    }

                    if (k == j){
                        break;
                    }

                    if (num[j] + num[k] == target){
                        lists.add(Arrays.asList(num[i], num[j], num[k]));
                    }
                }
            }
        }

        return lists;
    }

    /*
    * 别人的写法
    * */
    public static List<List<Integer>> solution3(int[] num){
//        Arrays.sort(nums);
//        List<List<Integer>> res = new LinkedList<>();
//        for (int i = 0; i < nums.length-2; i++) {
//            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
//                int lo = i+1, hi = nums.length-1, sum = 0 - nums[i];
//                while (lo < hi) {
//                    if (nums[lo] + nums[hi] == sum) {
//                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
//                        while (lo < hi && nums[lo] == nums[lo+1]) lo++;
//                        while (lo < hi && nums[hi] == nums[hi-1]) hi--;
//                        lo++; hi--;
//                    } else if (nums[lo] + nums[hi] < sum) lo++;
//                    else hi--;
//                }
//            }
//        }
//        return res;

        List<List<Integer>> result = new ArrayList<>();
        if (num != null && num.length >= 3){
            Arrays.sort(num);

            for (int i = 0 ; i < num.length - 2 ; i++){
                if (i == 0 || num[i] != num[i - 1]){
                    int j = i + 1;
                    int k = num.length - 1;
                    int target = -num[i];
                    while (k > j){
                        if (num[j] + num[k] == target){
                            result.add(Arrays.asList(num[i], num[j], num[k]));
                            while (k > j && num[j] == num[j + 1]){
                                j++;
                            }

                            while (k > j && num[k] == num[k - 1]){
                                k--;
                            }

                            j++;
                            k--;
                        }else if (num[j] + num[k] > target){
                            k--;
                        }else {
                            j++;
                        }
                    }
                }
            }
        }



        return result;
    }

    /*
     * 多重for循环
     * 但是不能避免num元素重复的情况
     * */
    public static List<List<Integer>> solution4(int[] num){
        List<List<Integer>> result = new ArrayList<>();
        if (num != null && num.length > 2){
            for (int i = 0 ; i < num.length ; i++){
                for (int j = i + 1 ; j < num.length ; j++){
                    for (int k = j + 1 ; k < num.length ; k++){
                        if (num[i] + num[j] + num[k] == 0){
                            result.add(Arrays.asList(num[i], num[j], num[k]));
                        }
                    }
                }
            }
        }

        return result;
    }
}
